{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Beautiful Pairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countBeautifulPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #美丽下标对的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> 。如果下标对 <code>i</code>、<code>j</code> 满足 <code>0 ≤ i &lt; j &lt; nums.length</code> ，如果&nbsp;<code>nums[i]</code> 的 <strong>第一个数字</strong> 和 <code>nums[j]</code> 的 <strong>最后一个数字</strong> <strong>互质</strong> ，则认为 <code>nums[i]</code> 和 <code>nums[j]</code> 是一组 <strong>美丽下标对</strong> 。</p>\n",
    "\n",
    "<p>返回 <code>nums</code> 中 <strong>美丽下标对</strong> 的总数目。</p>\n",
    "\n",
    "<p>对于两个整数 <code>x</code> 和 <code>y</code> ，如果不存在大于 1 的整数可以整除它们，则认为 <code>x</code> 和 <code>y</code> <strong>互质</strong> 。换而言之，如果 <code>gcd(x, y) == 1</code> ，则认为 <code>x</code> 和 <code>y</code> 互质，其中 <code>gcd(x, y)</code> 是 <code>x</code> 和 <code>k</code> <strong>最大公因数</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,5,1,4]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>nums 中共有 5 组美丽下标对：\n",
    "i = 0 和 j = 1 ：nums[0] 的第一个数字是 2 ，nums[1] 的最后一个数字是 5 。2 和 5 互质，因此 gcd(2,5) == 1 。\n",
    "i = 0 和 j = 2 ：nums[0] 的第一个数字是 2 ，nums[2] 的最后一个数字是 1 。2 和 5 互质，因此 gcd(2,1) == 1 。\n",
    "i = 1 和 j = 2 ：nums[1] 的第一个数字是 5 ，nums[2] 的最后一个数字是 1 。2 和 5 互质，因此 gcd(5,1) == 1 。\n",
    "i = 1 和 j = 3 ：nums[1] 的第一个数字是 5 ，nums[3] 的最后一个数字是 4 。2 和 5 互质，因此 gcd(5,4) == 1 。\n",
    "i = 2 和 j = 3 ：nums[2] 的第一个数字是 1 ，nums[3] 的最后一个数字是 4 。2 和 5 互质，因此 gcd(1,4) == 1 。\n",
    "因此，返回 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [11,21,12]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>共有 2 组美丽下标对：\n",
    "i = 0 和 j = 1 ：nums[0] 的第一个数字是 1 ，nums[1] 的最后一个数字是 1 。gcd(1,1) == 1 。\n",
    "i = 0 和 j = 2 ：nums[0] 的第一个数字是 1 ，nums[2] 的最后一个数字是 2 。gcd(1,2) == 1 。\n",
    "因此，返回 2 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= nums.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 9999</code></li>\n",
    "\t<li><code>nums[i] % 10 != 0</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-beautiful-pairs](https://leetcode.cn/problems/number-of-beautiful-pairs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-beautiful-pairs](https://leetcode.cn/problems/number-of-beautiful-pairs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,5,1,4]', '[11,21,12]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        return sum(gcd(int(str(a)[0]), b % 10) == 1 for a, b in combinations(nums, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range(len(nums)):\n",
    "            list1=list(str(nums[i]))\n",
    "            a=list1[0]\n",
    "            for h in range(i+1,len(nums)):\n",
    "                list2=list(str(nums[h]))\n",
    "                b=list2[-1]\n",
    "                if gcd(int(a),int(b))==1 :\n",
    "                     ans=ans+1\n",
    "        return ans\n",
    "\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "\n",
    "        ans, cnt = 0, [0] * 10\n",
    "\n",
    "        for x in nums:\n",
    "\n",
    "            for y in range(1, 10):\n",
    "\n",
    "                if cnt[y] and gcd(x % 10, y) == 1:\n",
    "\n",
    "                    ans += cnt[y]\n",
    "\n",
    "            while x >= 10: x //= 10  \n",
    "\n",
    "            cnt[x] += 1  \n",
    "\n",
    "        return ans\n",
    "\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nums_len = len(nums)\n",
    "        for i in range(nums_len):\n",
    "            for j in range(i+1, nums_len):\n",
    "                nums_i= nums[i]\n",
    "                nums_j = nums[j]\n",
    "                gcd_i = 0\n",
    "                while nums_i>0:\n",
    "                    div, mod = divmod(nums_i, 10)\n",
    "                    gcd_i = mod\n",
    "                    nums_i = div\n",
    "                # print(gcd_i)\n",
    "                gcd_j = nums_j%10\n",
    "                if math.gcd(gcd_i,gcd_j) == 1:\n",
    "                    ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        cnt = [0] * 10\n",
    "        for i, x in enumerate(nums):\n",
    "            y = x % 10\n",
    "            for j in range(10):\n",
    "                if gcd(y, j) == 1:\n",
    "                    ans += cnt[j]\n",
    "            while x >= 10:\n",
    "                x //= 10\n",
    "            cnt[x] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                x=int(str(nums[i])[0])\n",
    "                y=int(str(nums[j])[-1])\n",
    "                if gcd(x,y)==1:\n",
    "                    ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        coprime = {(i, j ) for i in range(1, 10) for j in range(1, 10) if gcd(i, j) == 1}\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                first = int(str(nums[i])[0])\n",
    "                last = nums[j] % 10\n",
    "                if (first, last) in coprime:\n",
    "                    ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        mp = [0] * 10\n",
    "        ans = 0\n",
    "        for n in nums:\n",
    "            st = int(str(n)[0])\n",
    "            en = int(str(n)[-1])\n",
    "            ans += mp[en]\n",
    "            for i in range(10):\n",
    "                if gcd(st,i) == 1:\n",
    "                    mp[i] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        ans, cnt = 0, [0] * 10\n",
    "        for x in nums:\n",
    "            for y in range(1, 10):\n",
    "                if cnt[y] and gcd(x % 10, y) == 1:\n",
    "                    ans += cnt[y]\n",
    "            while x >= 10: x //= 10\n",
    "            cnt[x] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        result, n = 0, len(nums)\n",
    "        for i in range(n-1):\n",
    "            x = int(str(nums[i])[0])\n",
    "            for j in range(i+1, n):\n",
    "                result += gcd(x, nums[j]%10) == 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        \n",
    "        def check(a, b):\n",
    "            if a == b and a != 1: return False\n",
    "            for i in range(2, 10):\n",
    "                if a % i == 0 and b % i == 0: return False\n",
    "            return True\n",
    "        \n",
    "        n = len(nums)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):\n",
    "                a, b = int(str(nums[i])[0]), nums[j] % 10\n",
    "                if check(a, b):\n",
    "                    ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        def firstNum(num):\n",
    "            while num // 10:\n",
    "                num //= 10\n",
    "            return num\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if math.gcd(firstNum(nums[i]),nums[j]%10) == 1:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        from math import gcd\n",
    "        len_i = len(nums) - 1\n",
    "        len_j = len_i + 1\n",
    "        index_ = 0\n",
    "        for i in range(len_i):\n",
    "            for j in range(i + 1, len_j):\n",
    "                if gcd(int(str(nums[i])[0]), nums[j]%10) == 1:\n",
    "                    index_ += 1\n",
    "        return index_\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        a = []\n",
    "        count = 0\n",
    "        for i in nums:\n",
    "            a.append(str(i))\n",
    "        for i in range(len(a)-1):\n",
    "            for j in range((i+1),len(a)):\n",
    "                if gcd(int(a[i][0]),int(a[j][-1]))==1:\n",
    "                    count += 1\n",
    "                    \n",
    "        return count\n",
    "                \n",
    "                        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        def gcd(a, b):\n",
    "            if min(a, b) == 1:\n",
    "                return 1\n",
    "            for i in range(2, min(a,b)+1):\n",
    "                if a % i == 0 and  b % i == 0:\n",
    "                    return False\n",
    "            return True\n",
    "            \n",
    "        ans = 0\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                numi = nums[i]\n",
    "                numj = nums[j] % 10\n",
    "                while numi >= 10:\n",
    "                    numi = numi // 10\n",
    "                if gcd(numi, numj):\n",
    "                    ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        count=0\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if gcd(int(str(nums[i])[0]),nums[j]%10)==1:\n",
    "                    count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        return sum(gcd(int(str(nums[i])[0]), int(str(nums[j])[-1])) == 1 for i in range(len(nums)) for j in range(i + 1, len(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        def gcd(a, b):\n",
    "            while b != 0:\n",
    "                temp = a % b\n",
    "                a = b\n",
    "                b = temp\n",
    "            return a == 1\n",
    "        res = 0\n",
    "        # 维护1-9互质数的数组\n",
    "        arr = [[0 for _ in range(10)] for _ in range(10)]\n",
    "        for i in range(1, 10):\n",
    "            for j in range(1, 10):\n",
    "                if gcd(i, j):\n",
    "                    arr[i][j] = 1\n",
    "        for i in range(len(nums) - 1):\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                a = int(str(nums[i])[0])\n",
    "                b = nums[j] % 10\n",
    "                if arr[a][b] == 1:\n",
    "                    res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        def huzhi(x, y):\n",
    "            if min(x,y)==1:\n",
    "                return True\n",
    "            if max(x,y)%min(x,y)==0:\n",
    "                return False\n",
    "            for i in range(2, min(x,y)):\n",
    "                if x%i==0 and y%i==0:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                # if math.gcd(nums[i], nums[j])==1:\n",
    "                #     ans += 1\n",
    "                if huzhi(int( str(nums[i])[0]), int( str(nums[j])[-1])):\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        ans, cnt = 0, [0] * 10\n",
    "        for x in nums:\n",
    "            for y in range(1, 10):\n",
    "                if cnt[y] and gcd(x % 10, y) == 1:\n",
    "                    ans += cnt[y]\n",
    "            while x >= 10: x //= 10  # 这里需要 O(log x) 的时间\n",
    "            cnt[x] += 1  # 统计最高位的出现次数\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        dic = {1: [], 2: [2, 4, 6, 8], 3: [3, 6, 9], 4: [2, 4, 6, 8], 5: [5],\n",
    "               6: [2, 3, 4, 6, 8, 9], 7: [7], 8: [2, 4, 6, 8], 9: [3, 6, 9]}\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            a = int(str(nums[i])[0])\n",
    "            for j in range(i + 1, n):\n",
    "                b = nums[j] % 10\n",
    "                if b not in dic[a]:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        ans, cnt = 0, [0] * 10\n",
    "        for x in nums:\n",
    "            for y in range(1, 10):\n",
    "                if cnt[y] and gcd(x % 10, y) == 1:\n",
    "                    ans += cnt[y]\n",
    "            while x >= 10: x //= 10  # 这里需要 O(log x) 的时间\n",
    "            cnt[x] += 1  # 统计最高位的出现次数\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nums_len = len(nums)\n",
    "        pre = [[0,0] for _ in range(nums_len)]\n",
    "        for i in range(nums_len):\n",
    "            v = nums[i]\n",
    "            v_i = v\n",
    "            gcd_i = 0\n",
    "            while v_i>0:\n",
    "                div, mod = divmod(v_i, 10)\n",
    "                gcd_i = mod\n",
    "                v_i = div\n",
    "            pre[i][0] = gcd_i\n",
    "            pre[i][1] = v%10\n",
    "       \n",
    "        for i in range(nums_len):\n",
    "            for j in range(i+1, nums_len):\n",
    "                nums_i= pre[i][0]\n",
    "                nums_j = pre[j][1]\n",
    "                if math.gcd(nums_i,nums_j) == 1:\n",
    "                    ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        pre = []\n",
    "        for v in nums:\n",
    "            v_i = v\n",
    "            gcd_i = 0\n",
    "            while v_i>0:\n",
    "                div, mod = divmod(v_i, 10)\n",
    "                gcd_i = mod\n",
    "                v_i = div\n",
    "            pre.append([gcd_i, v%10])\n",
    "        nums_len = len(nums)\n",
    "        for i in range(nums_len):\n",
    "            for j in range(i+1, nums_len):\n",
    "                nums_i= pre[i][0]\n",
    "                nums_j = pre[j][1]\n",
    "                if math.gcd(nums_i,nums_j) == 1:\n",
    "                    ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        cnt = [0]*10\n",
    "        ans = 0\n",
    "        for y in nums:\n",
    "            for x in range(1,10):\n",
    "                if gcd(y%10, x) == 1:\n",
    "                    ans += cnt[x]\n",
    "            while y>=10: y//=10\n",
    "            cnt[y] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nums_len = len(nums)\n",
    "        pre = [[0,0] for _ in range(nums_len)]\n",
    "        for i in range(nums_len):\n",
    "            v = nums[i]\n",
    "            v_i = v\n",
    "            gcd_i = 0\n",
    "            while v_i>0:\n",
    "                div, mod = divmod(v_i, 10)\n",
    "                gcd_i = mod\n",
    "                v_i = div\n",
    "            pre[i][0] = gcd_i\n",
    "            pre[i][1] = v%10\n",
    "       \n",
    "        for i in range(nums_len):\n",
    "            for j in range(i+1, nums_len):\n",
    "                nums_i= pre[i][0]\n",
    "                nums_j = pre[j][1]\n",
    "                if math.gcd(nums_i,nums_j) == 1:\n",
    "                    ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        ans, cnt = 0, [0] * 10\n",
    "        for x in nums:\n",
    "            for y in range(1, 10):\n",
    "                if cnt[y] and gcd(x % 10, y) == 1:\n",
    "                    ans += cnt[y]\n",
    "            while x >= 10:\n",
    "                x //= 10\n",
    "            cnt[x] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#import math\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        def gcd(num1, num2):\n",
    "            while num2:\n",
    "                num1, num2 = num2, num1 % num2\n",
    "            return num1\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            for j in range(i + 1, n):\n",
    "                if gcd(int(str(num)[0]), nums[j] % 10) <= 1:\n",
    "                    ans += 1\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        ans,n = 0,len(nums)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                num1 = int(str(nums[i])[0])\n",
    "                num2 = int(str(nums[j])[-1])\n",
    "                if math.gcd(num1,num2)==1:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            w = int(str(nums[i])[0])\n",
    "            for j in range(i+1, n):\n",
    "                y = nums[j] % 10\n",
    "                if math.gcd(w, y) == 1:\n",
    "                    ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        ans, cnt = 0, [0] * 10\n",
    "        for x in nums:\n",
    "            for y in range(1, 10):\n",
    "                if cnt[y] and gcd(x % 10, y) == 1:\n",
    "                    ans += cnt[y]\n",
    "            while x >= 10: x //= 10  # 这里需要 O(log x) 的时间\n",
    "            cnt[x] += 1  # 统计最高位的出现次数\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcd(a: int, b: int) -> int:\n",
    "        return gca(b, a%b) if b != 0 else a\n",
    "    \n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        res, cnt = 0, [0] * 10\n",
    "        for x in nums:\n",
    "            for y in range(10):\n",
    "                if gcd(x%10, y) == 1:\n",
    "                    res += cnt[y]\n",
    "            while x >= 10: x //= 10\n",
    "            cnt[x] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcd(a: int, b: int) -> int:\n",
    "        return gca(b, a%b) if b != 0 else a\n",
    "    \n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1, len(nums), 1):\n",
    "                s1 = str(nums[i])\n",
    "                s2 = str(nums[j])\n",
    "                if gcd(int(s1[0]), int(s2[-1])) == 1:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        cnt = [0 for _ in range(10)]\n",
    "        for x in nums:\n",
    "            for y in range(1, 10):\n",
    "                if cnt[y] and gcd(x % 10, y) == 1:\n",
    "                    res += cnt[y]\n",
    "            cnt[int(str(x)[0])] += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#import math\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        def gcd_custom(num1, num2):\n",
    "            while num2:\n",
    "                num1, num2 = num2, num1 % num2\n",
    "            return num1\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            for j in range(i + 1, n):\n",
    "                if gcd_custom(int(str(num)[0]), nums[j] % 10) <= 1:\n",
    "                    ans += 1\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        ans, cnt = 0, [0] * 10\n",
    "        for x in nums:\n",
    "            for y in range(1, 10):\n",
    "                if cnt[y] and gcd(x % 10, y) == 1:\n",
    "                    ans += cnt[y]\n",
    "            while x >= 10:\n",
    "                x //= 10\n",
    "            cnt[x] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        return sum(math.gcd(int(str(x)[0]), y % 10) == 1 for x, y in itertools.combinations(nums, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            for j in range(i + 1, n):\n",
    "                if gcd(int(str(x)[0]), int(str(nums[j])[-1])) == 1:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import gcd\n",
    "\n",
    "@cache\n",
    "def GCD(x,y):\n",
    "    return gcd(x, y)\n",
    "\n",
    "def first_digit(n):\n",
    "    return int(str(n)[0])\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        first = list(map(first_digit, nums))\n",
    "        last = [x%10 for x in nums]\n",
    "        return sum(1 for i, j in combinations(range(n), r=2) if GCD(first[i], last[j]) == 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        a = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if gcd(int(str(nums[i])[0]), nums[j] % 10) == 1:\n",
    "                    a += 1\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        gcd_mat = [ [gcd(i,j)  for i in range(10)] for j in range(10) ]\n",
    "        cnt = 0 \n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range( i+1, n ):\n",
    "                fir = int( str(nums[i])[0]) \n",
    "                sec = nums[j] % 10\n",
    "                if gcd_mat[fir][sec]==1:\n",
    "                    cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        # python 内置gcd函数\n",
    "        # def gcd(x,y):\n",
    "        #     while y!=0:\n",
    "        #         x,y=y,x%y\n",
    "        #     return x\n",
    "        res=0\n",
    "        cnt=[0]*10\n",
    "        for x in nums:\n",
    "            for i in range(1,10):\n",
    "                if cnt[i] and gcd(x%10,i)==1:\n",
    "                    res+=cnt[i]\n",
    "            cnt[int(str(x)[0])]+=1\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        import math\n",
    "        length = len(nums)\n",
    "        res = 0\n",
    "        for i in range(length-1):\n",
    "            for j in range(i+1,length):\n",
    "                n1 = int(str(nums[i])[0])\n",
    "                n2 = nums[j] % 10\n",
    "                if math.gcd(n1,n2) == 1:\n",
    "                    res += 1\n",
    "        return res \n",
    "'''2748. 美丽下标对的数目\n",
    "给你一个下标从 0 开始的整数数组 nums 。如果下标对 i、j 满足 0 ≤ i < j < nums.length ，如果 nums[i] 的 第一个数字 和 nums[j] 的 最后一个数字 互质 ，则认为 nums[i] 和 nums[j] 是一组 美丽下标对 。\n",
    "返回 nums 中 美丽下标对 的总数目。\n",
    "\n",
    "对于两个整数 x 和 y ，如果不存在大于 1 的整数可以整除它们，则认为 x 和 y 互质 。换而言之，如果 gcd(x, y) == 1 ，则认为 x 和 y 互质，其中 gcd(x, y) 是 x 和 k 最大公因数 。\n",
    "示例 1：\n",
    "输入：nums = [2,5,1,4]\n",
    "输出：5\n",
    "解释：nums 中共有 5 组美丽下标对：\n",
    "i = 0 和 j = 1 ：nums[0] 的第一个数字是 2 ，nums[1] 的最后一个数字是 5 。2 和 5 互质，因此 gcd(2,5) == 1 。\n",
    "i = 0 和 j = 2 ：nums[0] 的第一个数字是 2 ，nums[2] 的最后一个数字是 1 。2 和 5 互质，因此 gcd(2,1) == 1 。\n",
    "i = 1 和 j = 2 ：nums[1] 的第一个数字是 5 ，nums[2] 的最后一个数字是 1 。2 和 5 互质，因此 gcd(5,1) == 1 。\n",
    "i = 1 和 j = 3 ：nums[1] 的第一个数字是 5 ，nums[3] 的最后一个数字是 4 。2 和 5 互质，因此 gcd(5,4) == 1 。\n",
    "i = 2 和 j = 3 ：nums[2] 的第一个数字是 1 ，nums[3] 的最后一个数字是 4 。2 和 5 互质，因此 gcd(1,4) == 1 。\n",
    "因此，返回 5 。\n",
    "示例 2：\n",
    "输入：nums = [11,21,12]\n",
    "输出：2\n",
    "解释：共有 2 组美丽下标对：\n",
    "i = 0 和 j = 1 ：nums[0] 的第一个数字是 1 ，nums[1] 的最后一个数字是 1 。gcd(1,1) == 1 。\n",
    "i = 0 和 j = 2 ：nums[0] 的第一个数字是 1 ，nums[2] 的最后一个数字是 2 。gcd(1,2) == 1 。\n",
    "因此，返回 2 。\n",
    "提示：\n",
    "2 <= nums.length <= 100\n",
    "1 <= nums[i] <= 9999\n",
    "nums[i] % 10 != 0\n",
    "通过次数\n",
    "5.3K\n",
    "提交次数\n",
    "9.2K\n",
    "通过率\n",
    "57.5%'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        dat = [[0, 0] for _ in range(l)]\n",
    "        for i in range(l):\n",
    "            v = str(nums[i])\n",
    "            dat[i][0] = int(v[0])\n",
    "            dat[i][1] = int(v[-1])\n",
    "            \n",
    "        ret = 0\n",
    "        # print(f\"dat {dat}\")\n",
    "        for i in range(l):\n",
    "            for j in range(i + 1, l):\n",
    "                if 1 == gcd(dat[i][0], dat[j][1]):\n",
    "                    ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        res=0\n",
    "        count=[0]*10\n",
    "        for x in nums:\n",
    "            for y in range(1,10):\n",
    "                if count[y] and gcd(x%10,y)==1:\n",
    "                    res+=count[y]\n",
    "            while x>=10:\n",
    "                x//=10\n",
    "            count[x]+=1\n",
    "        return res\n",
    "        res=0\n",
    "        count=[0]*10\n",
    "        for x in nums:\n",
    "            for y in range(1,10):\n",
    "                if count[y]and gcd(x%10,y)==1:\n",
    "                    res+=count[y]\n",
    "            while x>10:\n",
    "                x//=10\n",
    "            count[x]+=1\n",
    "        return res\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            x = int(str(nums[i])[0])\n",
    "            for j in range(i+1, n):\n",
    "                y = nums[j] % 10\n",
    "                if math.gcd(x, y) == 1:\n",
    "                    res += 1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if math.gcd(int(str(nums[i])[0]), int(str(nums[j])[-1])) == 1:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        def gcd(m,n):\n",
    "            while m%n:\n",
    "                m,n = n,m%n \n",
    "            return n \n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                k = int(str(nums[i])[0])\n",
    "                t = int(str(nums[j])[-1])\n",
    "                if gcd(k,t) == 1:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        n = 0\n",
    "        for i in range(len(nums) - 1):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if gcd(int(str(nums[i])[:1]), int(str(nums[j])[-1:])) == 1: n += 1\n",
    "\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        # 暴力\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            s = str(nums[i])\n",
    "            nums[i] = int(s[0]), int(s[-1])\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if gcd(nums[i][0], nums[j][1]) == 1:\n",
    "                    ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        def gcd(m,n):\n",
    "            while m%n:\n",
    "                m,n=n,m%n \n",
    "            return n \n",
    "        def isP(m,n):\n",
    "            if gcd(m,n) == 1:\n",
    "                return True\n",
    "            return False\n",
    "        n=len(nums)\n",
    "        cnt=0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                a=str(nums[i])\n",
    "                b=str(nums[j])\n",
    "                if isP(int(a[0]),int(b[-1])):\n",
    "                    cnt+=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "\n",
    "        def gao(x):\n",
    "            if x>=1000:return x//1000 \n",
    "            if x>=100:return x//100\n",
    "            if x>=10:return x//10 \n",
    "            return x    \n",
    "        return sum(gcd(gao(nums[i])  ,nums[j] %10) ==1 for i in range(len(nums) -1 ) for j in range(i+1,len(nums)) )\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        cnt=[0]*10\n",
    "        res=0\n",
    "        for i in nums:\n",
    "            for j in range(1,10):\n",
    "                if cnt[j]>0 and gcd(i%10,j)==1:\n",
    "                    res+=cnt[j]\n",
    "            while i>=10:\n",
    "                i//=10\n",
    "            cnt[i]+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        def f(x):\n",
    "            a = x % 10\n",
    "            while x > 0:\n",
    "                a = x % 10 \n",
    "                x //= 10 \n",
    "            return a \n",
    "\n",
    "        for i in range(n):\n",
    "            a = f(nums[i])\n",
    "            for j in range(i+1, n):\n",
    "                b =  nums[j]%10\n",
    "                if math.gcd(a, b) == 1:\n",
    "                    ans += 1\n",
    "        return ans \n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        def gcd(a: int, b: int) -> int:\n",
    "            return a if b == 0 else gcd(b, a % b)\n",
    "        \n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            num1 = int(str(nums[i])[0])\n",
    "            for j in range(i + 1, n):\n",
    "                if gcd(num1, int(str(nums[j])[-1])) == 1:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        def last_digit(num):\n",
    "            return num % 10\n",
    "        def first_digit(num):\n",
    "            return int(str(num)[0])\n",
    "\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                ans += int(math.gcd(first_digit(nums[j]), last_digit(nums[i])) == 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        res=0\n",
    "        n=len(nums)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                if gcd(int(str(nums[i])[0]),int(str(nums[j])[-1]))==1:\n",
    "                    res+=1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "\n",
    "        ans, cnt = 0, [0] * 10\n",
    "        for x in nums:\n",
    "            for y in range(1, 10):\n",
    "                if cnt[y] and gcd(x % 10, y) == 1:\n",
    "                    ans += cnt[y]\n",
    "            while x >= 10: x //= 10  # 这里需要 O(log x) 的时间\n",
    "            cnt[x] += 1  # 统计最高位的出现次数\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        cnt = [0]*10\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            for key in range(1,10): #与之前的第一个字符比较计算\n",
    "                if cnt[key]>0 and gcd(num%10,key)==1:\n",
    "                    res += cnt[key]\n",
    "            while num>=10: #计算第一个字符\n",
    "                num //= 10\n",
    "            cnt[num] += 1\n",
    "        return res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            a = int(str(nums[i])[0])\n",
    "            for j in range(i + 1, n):\n",
    "                b = nums[j] % 10\n",
    "                if gcd(a, b) == 1:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        cnt = [0] * 10\n",
    "        ans = 0\n",
    "        for y in nums:\n",
    "            for x in range(1, 10):\n",
    "                if gcd(y % 10, x) == 1:\n",
    "                    ans += cnt[x]\n",
    "            while y >= 10: y //= 10\n",
    "            cnt[y] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "\n",
    "        def gcd(a, b):\n",
    "            return a if b == 0 else gcd(b, a%b)\n",
    "        def firstDigit(a):\n",
    "            while a >= 10:\n",
    "                a //= 10\n",
    "            return a\n",
    "        def lastDigit(a):\n",
    "            return a%10\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            a = nums[i]\n",
    "            l = firstDigit(a)\n",
    "            for j in range(i+1, n):\n",
    "                b = nums[j]\n",
    "                if gcd(l, lastDigit(b)) == 1:\n",
    "                    # print(a, b)\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "\n",
    "        count = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums)):\n",
    "                \n",
    "                if i<j:\n",
    "                    x = int(str(nums[i])[0])\n",
    "                    y = int(str(nums[j])[-1])\n",
    "                    if gcd(x,y) ==1:\n",
    "                        count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        cnt=[0]*10\n",
    "        res=0\n",
    "        for i in nums:\n",
    "            for j in range(1,10):\n",
    "                if gcd(i%10,j)==1:\n",
    "                    res+=cnt[j]\n",
    "            while i>=10:\n",
    "                i//=10\n",
    "            cnt[i]+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        def gcd(num1, num2):\n",
    "            while num2:\n",
    "                num1, num2 = num2, num1 % num2\n",
    "            return num1\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            for j in range(i + 1, n):\n",
    "                if math.gcd(int(str(num)[0]), nums[j] % 10) <= 1:\n",
    "                    ans += 1\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def firstnum(n):\n",
    "            while n >= 10:\n",
    "                n = n // 10\n",
    "            return n\n",
    "        \n",
    "        def gcd(a,b):\n",
    "            if not a % b:\n",
    "                return b\n",
    "            return gcd(b, a%b)\n",
    "\n",
    "        for i in range(0, len(nums)-1):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                x, y = firstnum(nums[i]), nums[j] % 10\n",
    "                if gcd(x, y) == 1:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        r = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if math.gcd(int(str(nums[i])[0]), nums[j]%10) == 1:\n",
    "                    r += 1\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        import math as m\n",
    "        n=len(nums)\n",
    "        i=0\n",
    "        j=1\n",
    "        out=0\n",
    "        for i in range(0,n-1):\n",
    "            for j in range(i+1,n):\n",
    "                a=str(nums[i])[0]\n",
    "                b=str(nums[j])[-1]\n",
    "                if m.gcd(int(a),int(b)) == 1:\n",
    "                    out+=1\n",
    "        return out        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nums_len = len(nums)\n",
    "        pre = [[0,0] for _ in range(nums_len)]\n",
    "        for i in range(nums_len):\n",
    "            v = nums[i]\n",
    "            v_i = v\n",
    "            gcd_i = 0\n",
    "            while v_i>0:\n",
    "                div, mod = divmod(v_i, 10)\n",
    "                gcd_i = mod\n",
    "                v_i = div\n",
    "            pre[i][0] = gcd_i\n",
    "            pre[i][1] = v%10\n",
    "        arr = [[0 for _ in range(10)] for _ in range(10)]\n",
    "        for i in range(1, 10):\n",
    "            for j in range(1, 10):\n",
    "                if math.gcd(i, j)==1:\n",
    "                    arr[i][j] = 1\n",
    "        for i in range(nums_len):\n",
    "            for j in range(i+1, nums_len):\n",
    "                nums_i= pre[i][0]\n",
    "                nums_j = pre[j][1]\n",
    "                if arr[nums_i][nums_j]:\n",
    "                    ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        cnt = [0] * 10\n",
    "        for num in nums:\n",
    "            for y in range(10):\n",
    "                if cnt[y] and gcd(num % 10, y) == 1:\n",
    "                    ans += cnt[y]\n",
    "            while num >= 10:\n",
    "                num //= 10\n",
    "            cnt[num] += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nums_len = len(nums)\n",
    "        pre = [[0,0] for _ in range(nums_len)]\n",
    "        for i in range(nums_len):\n",
    "            v = nums[i]\n",
    "            v_i = v\n",
    "            gcd_i = 0\n",
    "            while v_i>0:\n",
    "                div, mod = divmod(v_i, 10)\n",
    "                gcd_i = mod\n",
    "                v_i = div\n",
    "            pre[i][0] = gcd_i\n",
    "            pre[i][1] = v%10\n",
    "        arr = [[0 for _ in range(10)] for _ in range(10)]\n",
    "        for i in range(1, 10):\n",
    "            for j in range(1, 10):\n",
    "                if math.gcd(i, j)==1:\n",
    "                    arr[i][j] = 1\n",
    "        for i in range(nums_len):\n",
    "            for j in range(i+1, nums_len):\n",
    "                nums_i= pre[i][0]\n",
    "                nums_j = pre[j][1]\n",
    "                if arr[nums_i][nums_j]:\n",
    "                    ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        for i in range(n-1):\n",
    "            for j in range(1,n):\n",
    "                one = str(nums[i])[0]\n",
    "                unnoe = str(nums[j])[-1]\n",
    "                if i < j and gcd(int(one), int(unnoe)) == 1:\n",
    "                    count +=1\n",
    "        return count "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        dic = {1: [], 2: [2, 4, 6, 8], 3: [3, 6, 9], 4: [2, 4, 6, 8], 5: [5],\n",
    "               6: [2, 3, 4, 6, 8, 9], 7: [7], 8: [2, 4, 6, 8], 9: [3, 6, 9]}\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            a = int(str(nums[i])[0])\n",
    "            if a == 1:\n",
    "                ans += n - 1 - i\n",
    "                continue\n",
    "            for j in range(i + 1, n):\n",
    "                b = nums[j] % 10\n",
    "                if b not in dic[a]:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        ans, cnt = 0, [0] * 10\n",
    "        for x in nums:\n",
    "            for y in range(1, 10):\n",
    "                if cnt[y] and gcd(x % 10, y) == 1:\n",
    "                    ans += cnt[y]\n",
    "            while x >= 10: x //= 10\n",
    "            cnt[x] += 1\n",
    "            print(cnt[x])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBeautifulPairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        def gcd(a: int, b: int) -> int:\n",
    "            return a if b == 0 else gcd(b, a % b)\n",
    "        def f(x: int) -> int:\n",
    "            while x // 10 != 0:\n",
    "                x //= 10\n",
    "            return x\n",
    "        print(f(11))\n",
    "        cnt = 0\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                print((f(nums[i]), nums[j] % 10))\n",
    "                if gcd(f(nums[i]), nums[j] % 10) == 1:\n",
    "                    cnt += 1\n",
    "        return cnt\n",
    "                "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
